package com.practice.sequence;

/**
 * Given an positive integer array a. If a[i1] -> a[i2] -> ... -> a[i1], we
 * call that a cycle. There are two special cases:
 * 1. a[i] = i, that's the self cycle.
 * 2. a[i] > array size, that's also regarded as part of a cycle.
 * 
 * No duplicates exist in this array. 
 */
public class CountCycle {
	public int numberOfCycles(int[] a) {
		int cycle = 0;
		for (int i=0; i<a.length; i++) {
			if (a[i] >= a.length) cycle++;
			int t = i;
			while (a[t] > i && a[t] < a.length) t = a[t];
			if (a[t] == i) cycle++;
		}
		return cycle;
	}
}
